{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Time to Eat All Grains"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumTime"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #吃掉所有谷子的最短时间"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>一条线上有 <code>n</code> 只母鸡和 <code>m</code> 颗谷子。给定两个整数数组 <code>hens</code> 和 <code>grains</code> ，它们的大小分别为 <code>n</code> 和 <code>m</code> ，表示母鸡和谷子的初始位置。</p>\n",
    "\n",
    "<p>如果一只母鸡和一颗谷子在同一个位置，那么这只母鸡可以吃掉这颗谷子。吃掉一颗谷子的时间可以忽略不计。一只母鸡也可以吃掉多颗谷子。</p>\n",
    "\n",
    "<p>在 <code>1</code> 秒钟内，一只母鸡可以向左或向右移动 <code>1</code> 个单位。母鸡可以同时且独立地移动。</p>\n",
    "\n",
    "<p>如果母鸡行动得当，返回吃掉所有谷子的 <strong>最短</strong> 时间。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1 ：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>hens = [3,6,7], grains = [2,4,7,9]\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>\n",
    "母鸡吃掉所有谷子的一种方法如下：\n",
    "- 第一只母鸡在 1 秒钟内吃掉位置 2 处的谷子。\n",
    "- 第二只母鸡在 2 秒钟内吃掉位置 4 处的谷子。\n",
    "- 第三只母鸡在 2 秒钟内吃掉位置 7 和 9 处的谷子。 \n",
    "所以，需要的最长时间为2秒。 \n",
    "可以证明，在2秒钟之前，母鸡不能吃掉所有谷子。</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2 ：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>hens = [4,6,109,111,213,215], grains = [5,110,214]\n",
    "<b>输出：</b>1\n",
    "<b>解释：</b>\n",
    "母鸡吃掉所有谷子的一种方法如下：\n",
    "- 第一只母鸡在 1 秒钟内吃掉位置 5 处的谷子。\n",
    "- 第四只母鸡在 1 秒钟内吃掉位置 110 处的谷子。\n",
    "- 第六只母鸡在 1 秒钟内吃掉位置 214 处的谷子。\n",
    "- 其他母鸡不动。 \n",
    "所以，需要的最长时间为 1 秒。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= hens.length, grains.length &lt;= 2*10<sup>4</sup></code></li>\n",
    "\t<li><code>0 &lt;= hens[i], grains[j] &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-time-to-eat-all-grains](https://leetcode.cn/problems/minimum-time-to-eat-all-grains/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-time-to-eat-all-grains](https://leetcode.cn/problems/minimum-time-to-eat-all-grains/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,6,7]\\n[2,4,7,9]', '[4,6,109,111,213,215]\\n[5,110,214]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, time: List[int], totalTrips: int) -> int:\n",
    "        left = 1\n",
    "        right = totalTrips * max(time)\n",
    "\n",
    "        def is_valid(x):\n",
    "            count = 0\n",
    "            for t in time:\n",
    "                count += x // t\n",
    "                if count >= totalTrips:\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        while left < right:\n",
    "            mid = (right+left) // 2\n",
    "            if is_valid(mid):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid+1\n",
    "\n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, time: List[int], totalTrips: int) -> int:\n",
    "        def check(t, tol):\n",
    "            for ti in time:\n",
    "                tol -= (t // ti)\n",
    "                if tol <= 0: return True\n",
    "            return False\n",
    "        \n",
    "        l, r = 1, max(time) * totalTrips\n",
    "        while l < r:\n",
    "            m = (l + r) // 2\n",
    "            if check(m, totalTrips): r = m\n",
    "            else: l = m + 1\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, time: List[int], totalTrips: int) -> int:\n",
    "        left = min(time)\n",
    "        right = min(time) * totalTrips\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            total = 0\n",
    "            for t in time:\n",
    "                total += mid // t\n",
    "            if total >= totalTrips:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, time: List[int], totalTrips: int) -> int:\n",
    "        def trips(mid):\n",
    "            trips = 0\n",
    "            for i in time:\n",
    "                if mid // i == 0:\n",
    "                    break\n",
    "                trips += mid // i\n",
    "            return trips >= totalTrips\n",
    "\n",
    "        time.sort()\n",
    "        left = 1\n",
    "        right = totalTrips * max(time)\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if trips(mid):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, time: List[int], totalTrips: int) -> int:\n",
    "        l, r = 0, max(time) * totalTrips\n",
    "        while l + 1 < r:\n",
    "            m = l + r >> 1\n",
    "            if sum([m//x for x in time]) >= totalTrips:\n",
    "                r = m\n",
    "            else:\n",
    "                l = m\n",
    "        return r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, time: List[int], totalTrips: int) -> int:\n",
    "        maxT = min(time) * totalTrips + 1 #45\n",
    "        rate = sum([1/x for x in time]) \n",
    "        minT = floor(totalTrips/rate)\n",
    "        while minT < maxT:\n",
    "            midT = minT + (maxT - minT) //2\n",
    "            midTrips = sum([midT//x for x in time])\n",
    "            if midTrips < totalTrips:\n",
    "                minT = midT + 1\n",
    "            else:\n",
    "                maxT = midT\n",
    "                \n",
    "        return minT"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, time: List[int], totalTrips: int) -> int:\n",
    "        def hanshu(k):\n",
    "            res=0\n",
    "            for s in time:\n",
    "                res+=k//s\n",
    "            return res\n",
    "        return bisect_left(range(max(time)*totalTrips),totalTrips,key=hanshu)\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, time: List[int], totalTrips: int) -> int:\n",
    "        left, right = 0, 10 ** 14 + 1\n",
    "        while left < right - 1:\n",
    "            mid = (left + right) // 2\n",
    "            k = 0\n",
    "            for n in time:\n",
    "                k += mid // n\n",
    "            if k >= totalTrips:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid\n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, time: List[int], totalTrips: int) -> int:\n",
    "        n = len(time)\n",
    "        def check(t: int) -> bool:\n",
    "            f = [0]*n\n",
    "            for i in range(n):\n",
    "                f[i] = f[i-1] + t//time[i]\n",
    "            return f[-1] >= totalTrips\n",
    "        left = 1\n",
    "        right = max(time)*totalTrips\n",
    "        while left<right:\n",
    "            mid  = (left+right)//2\n",
    "            if check(mid):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid+1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, time: List[int], totalTrips: int) -> int:\n",
    "        \n",
    "        def check(t):\n",
    "            cnt = 0\n",
    "            for period in time:\n",
    "                cnt += t//period\n",
    "            return cnt>=totalTrips\n",
    "        \n",
    "\n",
    "        l = 0\n",
    "        r = max(time) * totalTrips\n",
    "\n",
    "        while l < r:\n",
    "            mid = (l+r)//2\n",
    "            \n",
    "            if check(mid):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid +1\n",
    "        \n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, time: List[int], totalTrips: int) -> int:\n",
    "        def count(k: int) -> int:\n",
    "            cnt = 0\n",
    "            for t in time:\n",
    "                cnt += k // t\n",
    "            return cnt\n",
    "\n",
    "        left, right = 1, max(time) * totalTrips\n",
    "        while left < right:\n",
    "            mid = (left + right) >> 1\n",
    "            if count(mid) < totalTrips:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def minimumTime(self, time: List[int], totalTrips: int) -> int:\n",
    "        lo, hi = 1, max(time) * totalTrips\n",
    "\n",
    "        while lo < hi:\n",
    "            md = lo + (hi - lo) // 2\n",
    "            if sum([md // t for t in time]) >= totalTrips: \n",
    "                hi = md\n",
    "            else:\n",
    "                lo = md + 1\n",
    "        return lo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, time: List[int], totalTrips: int) -> int:\n",
    "        \n",
    "        left = min(time)\n",
    "        right = totalTrips*left\n",
    "        while left<=right:\n",
    "            mid = (left+right)>>1\n",
    "            if sum([(mid)//t for t in time]) >=totalTrips:\n",
    "                right = mid-1\n",
    "            else:\n",
    "                left = mid+1\n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, time: List[int], totalTrips: int) -> int:\n",
    "        l = 1\n",
    "        ans = max(time) * len(time) * totalTrips\n",
    "        r = max(time) * len(time) * totalTrips\n",
    "        while l <= r:\n",
    "            mid = l + (r - l) // 2\n",
    "            t = sum([mid // i for i in time])\n",
    "            if t >= totalTrips:\n",
    "                r = mid - 1 \n",
    "                ans = min(ans , mid)\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, hens: List[int], grains: List[int]) -> int:\n",
    "        hens.sort()\n",
    "        grains.sort()\n",
    "        def check(threshold):\n",
    "            i, j = 0, 0\n",
    "            while i < len(hens):\n",
    "                left, right = hens[i], hens[i]\n",
    "                while j < len(grains):\n",
    "                    left = min(left, grains[j])\n",
    "                    right = max(right, grains[j])\n",
    "                    if min(hens[i] - left + right - left, right - hens[i] + right - left) <= threshold:\n",
    "                        j += 1\n",
    "                    else:\n",
    "                        break\n",
    "                i += 1\n",
    "            return j == len(grains)\n",
    "\n",
    "        l, r, res = 0, 2 * 10 ** 9, 0\n",
    "        while l <= r:\n",
    "            m = l + (r - l) // 2\n",
    "            if check(m):\n",
    "                res = m\n",
    "                r = m - 1\n",
    "            else:\n",
    "                l = m + 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, hens: List[int], grains: List[int]) -> int:\n",
    "      hens.sort()\n",
    "      grains.sort()\n",
    "      m,n=len(hens),len(grains)\n",
    "      def eatandrun(lh,lg,t):\n",
    "        if lg>lh+t or lg<lh-t:\n",
    "          return -1\n",
    "        if lg<lh:\n",
    "          ret=lh\n",
    "          tp1=t-(lh-lg)*2\n",
    "          tp2=(t-(lh-lg))//2\n",
    "          ret+=max(tp1,tp2)\n",
    "          return ret\n",
    "        else:\n",
    "          return lh+t      \n",
    "      def caneat(t):\n",
    "        i,j=0,0\n",
    "        ma=-1\n",
    "        while i<=m and j<n:\n",
    "          while j<n and ma>=grains[j]:\n",
    "            j+=1\n",
    "          if j==n:\n",
    "            return True\n",
    "          if i==m:\n",
    "            return False\n",
    "          ma=eatandrun(hens[i],grains[j],t)\n",
    "          while i<m-1 and ma==-1:\n",
    "            i+=1\n",
    "            ma=eatandrun(hens[i],grains[j],t)\n",
    "          i+=1\n",
    "        return j==n\n",
    "      return bisect.bisect_left(range(pow(10,10)),True,key=caneat)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, hens: List[int], grains: List[int]) -> int:\n",
    "        hens.sort()\n",
    "        grains.sort()\n",
    "        # print(hens)\n",
    "        # print(grains)\n",
    "        lo, hi = 0, 2*10**9\n",
    "        while lo <= hi:\n",
    "            t = (lo+hi)//2\n",
    "            n = len(grains)\n",
    "            j = 0\n",
    "            for g in hens:\n",
    "                pj = j\n",
    "                while j < n and min(abs(grains[pj]-g),abs(grains[j]-g))+grains[j]-grains[pj] <= t:\n",
    "                    j += 1\n",
    "                # print(g,j)\n",
    "            # print(t,j)\n",
    "            if j >= n:\n",
    "                hi = t-1\n",
    "            else:\n",
    "                lo = t+1\n",
    "        return lo \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, hens: List[int], grains: List[int]) -> int:\n",
    "        G,H = sorted(grains),sorted(hens)\n",
    "        m, n = len(G), len(H)\n",
    "\n",
    "        def check(t):\n",
    "            i = 0\n",
    "            for h in H:\n",
    "                j = i\n",
    "                while j<m and min(abs(h-G[j]),abs(h-G[i]))+G[j]-G[i]<=t:\n",
    "                    j += 1\n",
    "                i = j\n",
    "            return i==m\n",
    "\n",
    "        ma = abs(H[0]-G[0])+G[-1]-G[0]\n",
    "        return bisect_left(range(ma),True,key=check)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, hens: List[int], grains: List[int]) -> int:\n",
    "        m, n, hens, grains, l, r = len(hens), len(grains), sorted(hens), sorted(grains), 0, 2000000000\n",
    "        def g(x):\n",
    "            srt = 0\n",
    "            for i in hens:\n",
    "                last = max(0, i - grains[srt])\n",
    "                if last > x: return False\n",
    "                while srt < n and (last + 2 * (grains[srt] - i) <= x or last * 2 + grains[srt] - i <= x): srt += 1\n",
    "                if srt == n: return True\n",
    "            return False\n",
    "        while l < r:\n",
    "            mid = (l + r) // 2\n",
    "            if g(mid):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, hens: List[int], grains: List[int]) -> int:\n",
    "\n",
    "        hens.sort() # 注意题目没说有序，必须先排序，要保证鸡和粮食都是从左到右枚举\n",
    "        grains.sort()\n",
    "\n",
    "        def check(t):\n",
    "            p = 0\n",
    "            for j in range(len(hens)):\n",
    "                l = 0\n",
    "                r = 0\n",
    "                while p<len(grains):\n",
    "                    if grains[p]>hens[j]: #位于鸡右边的粮食，更新r\n",
    "                        r = max(r,grains[p]-hens[j])\n",
    "                    else: # 位于鸡左边的粮食，更新l\n",
    "                        l = max(l,hens[j]-grains[p])\n",
    "                    if min(l*2+r,r*2+l)<=t: # 只要两种掉头策略的最小值满足条件，这堆就可以吃\n",
    "                        p+=1\n",
    "                    else:\n",
    "                        break #这只鸡已经尽力了，换下一只\n",
    "            return p==len(grains) # 只有所有粮食都被吃了，才能返回True\n",
    "        \n",
    "        return bisect_left(range(max(hens)+max(grains)+1),1,key=check)\n",
    "\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, hens: List[int], grains: List[int]) -> int:\n",
    "        hens.sort()\n",
    "        grains.sort()\n",
    "        def check(threshold):\n",
    "            i, j = 0, 0\n",
    "            while i < len(hens):\n",
    "                left, right = hens[i], hens[i]\n",
    "                while j < len(grains):\n",
    "                    left, right = min(left, grains[j]), max(right, grains[j])\n",
    "                    if min(hens[i] - left + right - left, right - hens[i] + right - left) <= threshold:\n",
    "                        j += 1\n",
    "                    else:\n",
    "                        break\n",
    "                i += 1\n",
    "            return j == len(grains)\n",
    "        \n",
    "        l, r, res = 0, 2 * 10 ** 9, 0\n",
    "        while l <= r:\n",
    "            m = l + (r - l) // 2\n",
    "            if check(m):\n",
    "                res = m\n",
    "                r = m - 1\n",
    "            else:\n",
    "                l = m + 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    target is min movement\n",
    "    left = 0\n",
    "    right = longest distance between a hen and a grain\n",
    "\n",
    "    mid is the move for a hen to eat a grain\n",
    "    contraint is all grains should be eaten, and the hens should not exceed the li\n",
    "    convert move into grains\n",
    "    situation 1: when finish all moves, the number of grains > 0, it means the moves are too small\n",
    "    situation 2: when finish all moves, the number of grains <= 0, it means the moves are too large\n",
    "    '''\n",
    "    def minimumTime(self, hens: List[int], grains: List[int]) -> int:\n",
    "        hens = sorted(hens)\n",
    "        grains = sorted(grains)\n",
    "        left = 0\n",
    "        right = (max(grains[-1], hens[-1]) - min(grains[0], hens[0])) * 2\n",
    "\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "\n",
    "            if self.enough(hens, grains, mid):\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "\n",
    "        return left\n",
    "\n",
    "    def enough(self, hens, grains, mid):\n",
    "        index = 0\n",
    "        for i in range(len(hens)):\n",
    "            # hens is at the left of every grain\n",
    "            if hens[i] <= grains[index]:\n",
    "                dist = hens[i] + mid \n",
    "            # hens is at the right of left most \n",
    "            else:\n",
    "                left = hens[i] - grains[index]\n",
    "                if left > mid:\n",
    "                    return False \n",
    "                dist = max(hens[i] + mid - left * 2, hens[i] + (mid - left) // 2)\n",
    "            if grains[-1] <= dist:\n",
    "                return True\n",
    "            for j in range(index, len(grains)):\n",
    "                if grains[j] > dist:\n",
    "                    index = j\n",
    "                    break\n",
    "            \n",
    "        return False\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, hens: List[int], grains: List[int]) -> int:\n",
    "        m, n, hens, grains, l, r = len(hens), len(grains), sorted(hens), sorted(grains), 0, 2000000000\n",
    "        def g(x):\n",
    "            srt = 0\n",
    "            for i in hens:\n",
    "                last = max(0, i - grains[srt])\n",
    "                if last > x: return False\n",
    "                while srt < n and (last + 2 * (grains[srt] - i) <= x or last * 2 + grains[srt] - i <= x): srt += 1\n",
    "                if srt == n: return True\n",
    "            return False\n",
    "        while l < r:\n",
    "            mid = (l + r) // 2\n",
    "            if g(mid):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, hens: List[int], grains: List[int]) -> int:\n",
    "        hens.sort()\n",
    "        grains.sort()\n",
    "        def check(threshold):\n",
    "            i, j = 0, 0\n",
    "            while i < len(hens):\n",
    "                left, right = hens[i], hens[i]\n",
    "                while j < len(grains):\n",
    "                    left, right = min(left, grains[j]), max(right, grains[j])\n",
    "                    if min(hens[i] - left + right - left, right - hens[i] + right - left) <= threshold:\n",
    "                        j += 1\n",
    "                    else:\n",
    "                        break\n",
    "                i += 1\n",
    "            return j == len(grains)\n",
    "        \n",
    "        l, r, res = 0,  10 ** 9 + 5 * 10 ** 8, 0\n",
    "        while l <= r:\n",
    "            m = l + (r - l) // 2\n",
    "            if check(m):\n",
    "                res = m\n",
    "                r = m - 1\n",
    "            else:\n",
    "                l = m + 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, hens: List[int], grains: List[int]) -> int:\n",
    "        A,B = sorted(grains),sorted(hens)\n",
    "        m, n = len(A), len(B)\n",
    "\n",
    "        def check(t):\n",
    "            i = 0\n",
    "            for b in B:\n",
    "                j = i\n",
    "                while j<m and min(abs(b-A[j]),abs(b-A[i]))+A[j]-A[i]<=t:\n",
    "                    j += 1\n",
    "                i = j\n",
    "            return i==m\n",
    "        return bisect_left(range(B[0]+A[-1]),True,key=check)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, hens: List[int], grains: List[int]) -> int:\n",
    "\n",
    "        hens.sort() # 注意题目没说有序，必须先排序，要保证鸡和粮食都是从左到右枚举\n",
    "        grains.sort()\n",
    "\n",
    "        def check(t):\n",
    "            p = 0\n",
    "            for j in range(len(hens)):\n",
    "                l = 0\n",
    "                r = 0\n",
    "                while p<len(grains):\n",
    "                    if grains[p]>hens[j]: #位于鸡右边的粮食，更新r\n",
    "                        r = max(r,grains[p]-hens[j])\n",
    "                    else: # 位于鸡左边的粮食，更新l\n",
    "                        l = max(l,hens[j]-grains[p])\n",
    "                    if min(l*2+r,r*2+l)<=t: # 只要两种掉头策略的最小值满足条件，这堆就可以吃\n",
    "                        p+=1\n",
    "                    else:\n",
    "                        break #这只鸡已经尽力了，换下一只\n",
    "            return p==len(grains) # 只有所有粮食都被吃了，才能返回True\n",
    "        \n",
    "        return bisect_left(range(max(hens)+max(grains)+1),1,key=check)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, hens: List[int], grains: List[int]) -> int:\n",
    "        hens.sort()\n",
    "        grains.sort()\n",
    "        def f(x: int) -> bool:\n",
    "            last = -1\n",
    "            gidx = 0\n",
    "            for hen in hens:\n",
    "                gidx = bisect_right(grains, last, gidx)\n",
    "                if gidx == len(grains):\n",
    "                    return True\n",
    "                grain = grains[gidx]\n",
    "                if grain < hen:\n",
    "                    y = hen - grain\n",
    "                    if y > x:\n",
    "                        return False\n",
    "                    # grain   hen\n",
    "                    last = max(hen + x - y - y, hen + (x - y) // 2)\n",
    "                else:\n",
    "                    last = hen + x\n",
    "            gidx = bisect_right(grains, last, gidx)\n",
    "            if gidx == len(grains):\n",
    "                return True\n",
    "            return False\n",
    "        l = 0\n",
    "        r = abs(hens[0] - grains[0]) * 2 + abs(hens[0] - grains[-1])\n",
    "        while l < r - 1:\n",
    "            mid = (l + r) // 2\n",
    "            if f(mid):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid\n",
    "        if f(l):\n",
    "            return l\n",
    "        else:\n",
    "            return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, hens: List[int], grains: List[int]) -> int:\n",
    "        hens.sort()\n",
    "        grains.sort()\n",
    "        def check(threshold):\n",
    "            i, j = 0, 0\n",
    "            while i < len(hens):\n",
    "                left, right = hens[i], hens[i]\n",
    "                while j < len(grains):\n",
    "                    left, right = min(left, grains[j]), max(right, grains[j])\n",
    "                    if min(hens[i] - left + right - left, right - hens[i] + right - left) <= threshold:\n",
    "                        j += 1\n",
    "                    else:\n",
    "                        break\n",
    "                i += 1\n",
    "            return j == len(grains)\n",
    "        \n",
    "        l, r, res = 0, 2 * 10 ** 9, 0\n",
    "        while l <= r:\n",
    "            m = l + (r - l) // 2\n",
    "            if check(m):\n",
    "                res = m\n",
    "                r = m - 1\n",
    "            else:\n",
    "                l = m + 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, a: List[int], b: List[int]) -> int:\n",
    "        a.sort()\n",
    "        b.sort()\n",
    "        l, r = 0, 2*10**9\n",
    "        while l < r:\n",
    "            mid = (l + r) // 2\n",
    "            ok = 1\n",
    "            j = 0\n",
    "            left = 0\n",
    "            for i in b:\n",
    "                while True:\n",
    "                    if a[j] < i:\n",
    "                        if 2*left + i - a[j] <= mid:\n",
    "                            break\n",
    "                        if 2*(i-a[j]) + left <= mid:\n",
    "                            break\n",
    "                    else:\n",
    "                        if a[j] - i <= mid:\n",
    "                            left = max(left, a[j] - i)\n",
    "                            break\n",
    "                        else:\n",
    "                            ok = 0\n",
    "                            break\n",
    "                    j += 1\n",
    "                    left = 0\n",
    "                    if j >= len(a):\n",
    "                        ok = 0\n",
    "                        break\n",
    "                if not ok:\n",
    "                    break\n",
    "            if not ok:\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, hens: List[int], grains: List[int]) -> int:\n",
    "        A,B = sorted(grains),sorted(hens)\n",
    "        m, n = len(A), len(B)\n",
    "\n",
    "        def check(t):\n",
    "            i = 0\n",
    "            for b in B:\n",
    "                j = i\n",
    "                while j<m and min(abs(b-A[j]),abs(b-A[i]))+A[j]-A[i]<=t:\n",
    "                    j += 1\n",
    "                i = j\n",
    "            return i==m\n",
    "        ma = abs(B[0]-A[0])+A[-1]-A[0]\n",
    "        return bisect_left(range(ma),True,key=check)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumTime(self, hens: List[int], grains: List[int]) -> int:\n",
    "        hens.sort()\n",
    "        grains.sort()\n",
    "        def judge(time):\n",
    "            i = 0\n",
    "            for j in range(len(hens)):\n",
    "                if i == len(grains):\n",
    "                    return True\n",
    "                if grains[i] < hens[j]:\n",
    "                    if grains[i] < hens[j] - time:\n",
    "                        return False\n",
    "                    t1 = time - hens[j] + grains[i]\n",
    "                    t2 = time - 2 * (hens[j] - grains[i])\n",
    "                    x = hens[j] + max(t1 // 2, t2)\n",
    "                    while i < len(grains) and grains[i] <= x:\n",
    "                        i += 1\n",
    "                else:\n",
    "                    x = hens[j] + time\n",
    "                    while i < len(grains) and grains[i] <= x:\n",
    "                        i += 1\n",
    "            return i == len(grains)\n",
    "\n",
    "        l, r = 0, 2 * 10 ** 9\n",
    "        while l < r:\n",
    "            mid = (l + r) // 2\n",
    "            if judge(mid):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
